package com.dailywork.basepro.heap;

import java.util.*;
import java.util.Map.Entry;
import java.util.stream.Collectors;

public class SelfHeap1 {

    public static void main(String[] args) {
        int[] barcodes =
                new int[]{
                        51, 83, 51, 40, 51, 40, 51, 40, 83, 40, 83, 83, 51, 40, 40, 51, 51, 51, 40, 40, 40, 83,
                        51, 51, 40, 51, 51, 40, 40, 51, 51, 40, 51, 51, 51, 40, 83, 40, 40, 83, 51, 51, 51, 40,
                        40, 40, 51, 51, 83, 83, 40, 51, 51, 40, 40, 40, 51, 40, 83, 40, 83, 40, 83, 40, 51, 51,
                        40, 51, 51, 51, 51, 40, 51, 83, 51, 83, 51, 51, 40, 51, 40, 51, 40, 51, 40, 40, 51, 51,
                        51, 40, 51, 83, 51, 51, 51, 40, 51, 51, 40, 40
                };
        //    int[] barcodes = new int[]{9,9,9,9,9,10,10,10,10,5,5,5,5,5,5,5,5};
        System.out.println(
                Arrays.stream(rearrangeBarcodes(barcodes))
                        .mapToObj(String::valueOf)
                        .collect(Collectors.joining(",")));
    }

    private static int[] rearrangeBarcodes(final int[] barcodes) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int value : barcodes) {
            if (!map.containsKey(value)) {
                List<Integer> list = new ArrayList<>();
                list.add(value);
                map.put(value, list);
            } else {
                map.get(value).add(value);
            }
        }
        List<Map.Entry<Integer, List<Integer>>> temp =
                map.entrySet().stream()
                        .sorted(
                                (list1, list2) -> Integer.compare(list2.getValue().size(), list1.getValue().size()))
                        .collect(Collectors.toList());
        map.clear();
        int count = 1;
        List<Integer> result = new ArrayList<>(barcodes.length);
        int size = 0;
        for (Map.Entry<Integer, List<Integer>> entry : temp) {
            List<Integer> values = entry.getValue();
            if (result.isEmpty()) {
                result.addAll(values);
                size = values.size();
            } else {
                for (Integer value : values) {
                    if (count > result.size()) {
                        result.add(value);
                        size = result.size();
                    } else {
                        result.add(count, value);
                    }
                    count = count + 2;
                    if (count > size * 2 - 1) {
                        count = 0;
                    }
                }
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    private int[] rearrangeBarcodes1(final int[] barcodes) {

        Map<Integer, Integer> m = new HashMap<Integer, Integer>();

        for (Integer code : barcodes) {
            if (m.get(code) != null) {
                m.put(code, m.get(code) + 1);
                continue;
            }

            m.put(code, 1);
        }

        ArrayList<Entry<Integer, Integer>> list =
                new ArrayList<Map.Entry<Integer, Integer>>(m.entrySet());
        Collections.sort(
                list,
                new Comparator<Entry<Integer, Integer>>() {
                    @Override
                    public int compare(Map.Entry<Integer, Integer> arg0, Map.Entry<Integer, Integer> arg1) {
                        return arg1.getValue() - arg0.getValue();
                    }
                });

        int j = 0;
        int[] res = new int[barcodes.length];
        for (int i = 0; i < list.size(); i++) {
            Integer value = list.get(i).getValue();
            while (value > 0) {
                res[j] = list.get(i).getKey();
                j = j + 2;
                if (j > barcodes.length - 1) {
                    j = 1;
                }
                value = value - 1;
            }
        }

        return res;
    }
}
